Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prova scritta del 19 Dicembre 2002

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 18}.

1. Determinare quante sono le funzioni f : A → A iniettive. SOLUZIONE: 18!.

2. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene almeno un numero dispari. SOLUZIONE: 18^{18} − 9^{18}. Conto tutte le funzioni, che sono 18^{18}, meno quelle che assumono solo valori pari, che sono 9^{18}.

3. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene al massimo un numero pari. SOLUZIONE: 9^{18}+9(10^{18}−9^{18}). Quelle la cui immagine non contiene numeri pari sono 9^{18} (ci sono 9 numeri dispari, e devo scegliere una successione di 18 numeri dispari). A queste devo aggiungere quelle la cui immagine contiene esattamente un numero pari. Queste sono 9(10^{18} − 9^{18}). Il fattore 9 davanti alle parentesi si giustifica con il fatto che il numero pari lo posso scegliere in 9 modi. Una volta scelto il numero pari, ci sono 10 valori possibili per la funzione (i 9 dispari più il pari scelto) e questo mi dà 10^{18} funzioni. Devo però togliere da queste quelle che non assumono il valore pari scelto, che sono 9^{18}.

4. Determinare quante sono le funzioni f : A → A tali che esistano almeno due elementi a e b di A in modo che valga f(a) = f(b). SOLUZIONE: 18^{18}−18!, ovvero tutte le funzioni meno quelle iniettive.

NOTA: Si possono indicare le soluzioni tramite una espressione senza svolgere i calcoli. Le risposte devono essere giustificate.

Esercizio 2. Si consideri la successione di Fibonacci definita da f_{0} = 0, f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che:

1. f_{5n} = 5f_{5n−4} + 3f_{5n−5} per ogni n ≥ 1. SOLUZIONE: per sostituzione f_{5n} = f_{5n−1}+f_{5n−2} = (f_{5n−2}−f_{5n−3})+(f_{5n−3}+f_{5n−4}). Ora sostituisco f_{5n−3} con f_{5n−4} + f_{5n−5}, e f_{5n−2} con f_{5n−3} + f_{5n−4}, che è uguale a f_{5n−4} +f_{5n−5} +f_{5n−4}. Effettuando le sostituzioni e sommando ottengo la formula.

2. Per ogni n ≥ 1, f_{5n} è multiplo di 5. SOLUZIONE: Per induzione forte usando la formula del punto precedente. Abbiamo f_{0} = 0, f_{1} = 1, f_{2} = 1, f_{3} = 2, f_{4} = 3, f_{5} = 5, da cui si vede che la base dell’induzione (il caso n = 1) è verificata (in effetti funziona anche per n = 0). Per il passo induttivo osserviamo che f_{5n} è la somma di 5f_{5n−4}, che è senz’altro un multiplo di 5, e di f_{5n−5} = f_{5(n−1)}, che per ipotesi induttiva è un multiplo di 5. Concludiamo osservando che la somma di due multipli di 5 è un multiplo di 5.

Esercizio 3. Trovare tutte le soluzioni x ∈ ℤ della congruenza

30x ≡ 70 (mod 55)

SOLUZIONE. Dividendo tutto per 5 ottengo la congruenza equivalente 6x ≡ 14 (mod 11), che si può anche scrivere come 3x ≡ 7 (mod 11) dividendo per 2 i due termini della congruenza (è lecito perché (2, 11) = 1). Ora osservo che 4 è un inverso di 3 modulo 11 in quanto 4 · 3 = 12, che è congruo a 1 modulo 11 (tale inverso si può anche trovare con l’algoritmo per il teorema di Bezout). Moltiplicando per 4 i due termini della congruenza ottengo 4 · 3x ≡ 4 · 7 (mod 11), e semplificando x ≡ 6 (mod 11). Una soluzione è x = 6. Le altre sono gli interi della forma 6 + k11.

Esercizio 4. Determinare nella seguente lista se vi siano due espressioni che denotano lo stesso insieme, qualunque sia la scelta degli insiemi A, B, C. La risposta deve essere giustificata.

1. (A × C) ∪ (B × C)

2. (A ∪ C) × (B ∪ C)

3. (A ∪ B) × C

4. (A × B) ∪ C

SOLUZIONE: La prima e la terza denotano lo stesso insieme. Infatti la terza è uguale a {(x, c) | x ∈ A ∪ B ∧ c ∈ C}, che usando la definizione di unione si riscrive come {(x, c) | (x ∈ A ∨ x ∈ B) ∧ c ∈ C}. Ora uso la distributività di ∧ su ∨ per ottenere {(x, c) | (x ∈ A ∧ c ∈ C) ∨ (x ∈ B ∧ c ∈ C)}, che è uguale a {(x, c) | x ∈ A ∧ c ∈ C} ∪ {(x, c) | x ∈ B ∧ c ∈ C}, che coincide con l’insieme dato dalla prima espressione.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 22}.

1. Determinare quante sono le funzioni f : A → A iniettive. SOLUZIONE. 22!.

2. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene al massimo un numero dispari. SOLUZIONE. 11^{22} + 11(12^{22} + 11^{22}).

3. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene almeno un numero pari. SOLUZIONE: 22^{22} − 11^{22}.

4. Determinare quante sono le funzioni f : A → A tali che esistano al più due elementi a e b di A in modo che valga f(a) = f(b). 22!+\binom{22}{2}·22·21!.

NOTA: Si possono indicare le soluzioni tramite una espressione senza svolgere i calcoli. Le risposte devono essere giustificate.

Esercizio 2. Si consideri la successione di Fibonacci definita da f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che:

1. f_{3n} = 2f_{3n−2} + f_{3n−3} per ogni n ≥ 1.

2. Per ogni n ≥ 1, f_{3n} è pari.

Esercizio 3. Trovare tutte le soluzioni x ∈ ℤ della congruenza

12x ≡ 32 (mod 52)

SOLUZIONE x ≡ 7 (mod 7).

Esercizio 4. Determinare nella seguente lista se vi siano due espressioni che denotano lo stesso insieme, qualunque sia la scelta degli insiemi X, Y, Z. La risposta deve essere giustificata.

1. (X ∩ Y) × Z

2. (X × Z) ∩ (Y × Z)

3. (X ∩ Z) × (Y ∩ Z)

4. X ∩ (Y × Z)

SOLUZIONE. La prima e la seconda.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 19}.

1. Determinare quante sono le funzioni f : A → A iniettive. SOLUZIONE. 19!.

2. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene esattamente un numero dispari. SOLUZIONE. 10(10^{19}−9^{19}).

3. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene al massimo un numero pari. SOLUZIONE. 10^{19} + 9(11^{19} − 10^{19}).

4. Determinare quante sono le funzioni f : A → A tali che esistano al più due elementi a e b di A in modo che valga f(a) = f(b). SOLUZIONE. 19! + \binom{19}{2}19 · 18!.

NOTA: Si possono indicare le soluzioni tramite una espressione senza svolgere i calcoli. Le risposte devono essere giustificate.

Esercizio 2. Si consideri la successione di Fibonacci definita da f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che:

1. f_{4n} = 3f_{4n−3} + 2f_{4n−4} per ogni n ≥ 1.

2. Per ogni n ≥ 1, f_{4n} è multiplo 3.

Esercizio 3. Trovare tutte le soluzioni x ∈ ℤ della congruenza

18x ≡ 36 (mod 42)

SOLUZIONE. x ≡ 2 (mod 7).

Esercizio 4. Determinare nella seguente lista se vi siano due espressioni che denotano lo stesso insieme, qualunque sia la scelta degli insiemi X, Y, Z. La risposta deve essere giustificata.

1. A × (B ∩ C)

2. A ∩ (B × C)

3. (A ∩ B) × (A ∩ C)

4. (A × B) ∩ (A × C)

SOLUZIONE: La 1 e la 4.

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Numero di matricola: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Sia A = {n ∈ ℕ | 1 ≤ n ≤ 21}.

1. Determinare quante sono le funzioni f : A → A iniettive. SOLUZIONE. 21!.

2. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene al massimo un numero dispari. SOLUZIONE. 10^{21} + 11(11^{21} − 10^{21}).

3. Determinare quante sono le funzioni f : A → A tali che l’immagine di f contiene esattamente un numero pari. SOLUZIONE. 10(12^{21}−11^{21}).

4. Determinare quante sono le funzioni f : A → A tali che esistano almeno due elementi a e b di A in modo che valga f(a) = f(b). SOLUZIONE. 21^{21} − 21!.

NOTA: Si possono indicare le soluzioni tramite una espressione senza svolgere i calcoli. Le risposte devono essere giustificate.

Esercizio 2. Si consideri la successione di Fibonacci definita da f_{1} = 1, f_{2} = 1, f_{n+2} = f_{n+1} + f_{n}. Dimostrare che:

1. f_{6n} = 8f_{6n−5} + 5f_{6n−6} per ogni n ≥ 1.

2. Per ogni n ≥ 1, f_{6n} è multiplo 4.

Esercizio 3. Trovare tutte le soluzioni x ∈ ℤ della congruenza

24x ≡ 30 (mod 78)

SOLUZIONE x ≡ 11 (mod 13).

Esercizio 4. Determinare nella seguente lista se vi siano due espressioni che denotano lo stesso insieme, qualunque sia la scelta degli insiemi X, Y, Z. La risposta deve essere giustificata.

1. (X × Y) ∪ Z

2. (X × Y) ∪ (X × Z)

3. X × (Y ∪ Z)

4. (X ∪ Z) × (Y ∪ Z)

SOLUZIONE. La 2 e la 3.